/*
 * @Autor: taobo
 * @Date: 2020-06-09 18:27:48
 * @LastEditTime: 2020-06-09 19:08:00
 * @Description: LRU
 */ 
#include <bits/stdc++.h>
using namespace std;
class LRU{
private:
    struct Node{
        int key;
        int val;
        Node(int k,int v):key(k),val(v){}
    };
private:
    int capacity;
    list<Node> cacheList;
    unordered_map<int,list<Node>::iterator> cacheMap;
    mutex mtx;
public:
    LRU(int c):capacity(c){}
    int Get(int k){
        lock_guard<mutex> lck(mtx);
        if(cacheMap.find(k) != cacheMap.end()){
            cacheList.splice(cacheList.begin(),cacheList,cacheMap[k]);
            cacheMap[k] = cacheList.begin();
            return cacheMap[k]->val;
        }
        return -1;
    }
    void Put(int k, int v){
        lock_guard<mutex> lck(mtx);
        if(cacheMap.find(k) != cacheMap.end()){
            cacheMap[k]->val = v;
            cacheList.splice(cacheList.begin(),cacheList,cacheMap[k]);
            cacheMap[k] = cacheList.begin();
        }else{
            if(cacheList.size() == capacity){
                cacheMap.erase(cacheList.back().key);
                cacheList.pop_back();
            }
            cacheList.emplace_front(k,v);
            cacheMap[k] = cacheList.begin();
        }
    }
};
static shared_ptr<LRU> lrucache;
void Func(int i)
{
    std::this_thread::sleep_for(std::chrono::seconds(i));
    lrucache->Put(1,2);
    cout <<i<<": "<<std::this_thread::get_id() <<" addr: "<< lrucache << endl;
}

int main()
{
    lrucache = make_shared<LRU>(20);
    vector<thread> threads;
    for(int i=0;i<30;++i){
        threads.emplace_back(Func,i);
    }
    for(int i=0;i<30;++i){
        threads[i].join();
    }
    return 0;
}